/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/zigzag-iterator
   @Language: C++
   @Datetime: 19-05-06 13:42
   */

class ZigzagIterator {
	vector<int> *v1, *v2;
	int id, id1, id2;
public:
	/*
	 * @param v1: A 1d vector
	 * @param v2: A 1d vector
	 */
	ZigzagIterator(vector<int>& v1, vector<int>& v2) {
		// do intialization if necessary
		id=id1=id2=0;
		this->v1=&v2;
		this->v2=&v1;
	}

	/*
	 * @return: An integer
	 */
	int next() {
		// write your code here
		if((id&1 && id1<v1->size()) || id2>=v2->size()){
			id++;
			return (*v1)[id1++];
		}
		else{
			id++;
			return (*v2)[id2++];
		}
	}

	/*
	 * @return: True if has next
	 */
	bool hasNext() {
		// write your code here
		return id1<v1->size() || id2<v2->size();
	}
};

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator solution(v1, v2);
 * while (solution.hasNext()) result.push_back(solution.next());
 * Ouptut result
 */
